|
In mathematical analysis and computer science, Z-order, Morton order, or Morton code is a function which maps multidimensional data to one dimension while preserving locality of the data points. It was introduced in 1966 by G. M. Morton. The z-value of a point in multidimensions is simply calculated by interleaving the binary representations of its coordinate values. Once the data are sorted into this ordering, any one-dimensional data structure can be used such as binary search trees, B-trees, skip lists or (with low significant bits truncated) hash tables. The resulting ordering can equivalently be described as the order one would get from a depth-first traversal of a quadtree. ==Coordinate values== The figure below shows the Z-values for the two dimensional case with integer coordinates 0 ≤ ''x'' ≤ 7, 0 ≤ ''y'' ≤ 7 (shown both in decimal and binary). Interleaving the binary coordinate values yields binary ''z''-values as shown. Connecting the ''z''-values in their numerical order produces the recursively Z-shaped curve. Two-dimensional Z-values are also called as quadkey ones. The Z-values of x's are described as binary numbers: x | 0b101010) + x()) & 0b01010101 x() = (x() - x()) & 0b01010101 if i >= j 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Z-order curve」の詳細全文を読む スポンサード リンク
|